package leetcode.d_300_plus;

import java.util.Arrays;

public class P2099 {
    public static void main(String[] args) {
        P2099.Solution solution = new P2099().new Solution();
        System.out.println(Arrays.toString(solution.maxSubsequence(new int[]{2,1,3,3}, 2)));
        System.out.println(Arrays.toString(solution.maxSubsequence2(new int[]{2,1,3,3}, 2)));
    }
    // https://leetcode.cn/problems/find-subsequence-of-length-k-with-the-largest-sum/description/
    // 找到和为最大的长度为K的子序列
    class Solution {
        public int[] maxSubsequence(int[] nums, int k) {
            int len = nums.length;
            // idxMap：辅助数组，用来存储数值和索引
            int idxMap[][] = new int[len][2];
            for(int idx = 0; idx < len; idx++){
                idxMap[idx][1] = nums[idx];
                idxMap[idx][0] = idx;
            }
            // 按照数值nums[idx]从大到小排序
            Arrays.sort(idxMap, (a, b) -> b[1] - a[1]);
            // 按照索引idx从小到大进行排列
            Arrays.sort(idxMap, 0, k, (a, b) -> a[0] - b[0]);

            // 复制结果
            int[] res = new int[k];
            for(int idx = 0; idx < k; idx++){
                res[idx] = idxMap[idx][1];
            }

            return res;
        }

        public int[] maxSubsequence2(int[] nums, int k) {
            int n  = nums.length;
            int[][] idxMap = new int[n][2];
            for (int i=0; i<n; i++) {
                idxMap[i][0] = nums[i];
                idxMap[i][1] = i;
            }
            Arrays.sort(idxMap, (v1, v2)-> v2[0] - v1[0]);
            int[] index = new int[k];
            for (int i=0; i<k; i++) {
                index[i] = idxMap[i][1];
            }
            Arrays.sort(index);
            int[] res = new int[k];
            for (int i=0; i<k; i++) {
                res[i] = nums[index[i]];
            }
            return res;
        }
    }
}
